<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" >
<head>
<title>Maze Generator for the Maze Simulator</title>
<link href="../Styles/Standard.css" rel="stylesheet" type="text/css" />
</head>
<body>
<table width="100%">
<tr>
<td width="200"><a href="http://www.ProMRDS.com"><img src="../Images/HomeIcon.gif" alt="ProMRDS Home Page" border="0" width="200" height="60" /></a></td>
<td width="*" align="center"><img src="Images/MazeGenerator.gif" alt="Maze Generator" /></td>
</tr>
<tr>
<td colspan="2"><hr /></td>
</tr>
</table>

<div class="page">
<p class="heading"><span class="smallhead">Professional</span><br />&nbsp;&nbsp;&nbsp;Microsoft Robotics Developer Studio<br />
<a href="http://www.ProMRDS.com" onmouseout="Home.src='../Images/Home.gif';" onmouseover="Home.src='../Images/Home_f2.gif';"><img name="Home" src="../Images/Home.gif" width="150" height="25" border="0" alt="Home Page" /></a>
<a href="../ReadMe.htm" onmouseout="Contents.src='../Images/Contents.gif';" onmouseover="Contents.src='../Images/Contents_f2.gif';"><img name="Contents" src="../Images/Contents.gif" width="150" height="25" border="0" alt="Book Contents" /></a>
<a href="ReadMe.htm" onmouseout="ThisChapter.src='../Images/ThisChapter.gif';" onmouseover="ThisChapter.src='../Images/ThisChapter_f2.gif';"><img name="ThisChapter" src="../Images/ThisChapter.gif" width="150" height="25" border="0" alt="This Chapter" /></a>
</p>

<h1>Maze Generator for the Maze Simulator</h1>

<h2>Background</h2>
<p>
Having a Maze Simulator raises the obvious question of how to create
mazes in the first place. A simple program is provided that can be
used to generate new mazes using the Depth-First Search algorithm.
</p>
<a href="Images/Maze.jpg"><img src="images/Maze_small.jpg" alt="Generated Maze" border="0" /></a>
<p>
If you click on the image to see a larger view, and look very closely
near the green wall segment at the left-hand side (the start point)
you might just see the Pioneer robot and the bright red dots from
the Laser Range Finder hitting the wall.
</p>
<p>
To set up a new maze there are several steps you need to take:
</p>
<ul>
<li>Create a new bitmap image using the Maze Generator.</li>
<li>Edit the Maze Simulator configuration file and change it as appropriate.</li>
<li>Write your own service to use to solve the maze using the Webcam and/or Laser Range Finder on the simulated Pioneer robot.</li>
</ul>

<h3>Creating a new Maze Bitmap Image</h3>
<p>
Run the Maze Generator. Select the Maze Parameters from the Options menu:
</p>
<ul>
<li>Number of Grid Blocks per row</li>
<li>Grid Block size</li>
<li>Wall Thickness</li>
</ul>
<p>
The generated mazes are always square. (If you want rectangular, then you will
have to modify the code). Therefor the number of Grid Blocks per row is
also the number of columns.
</p>
<p>
The Grid Block size is the number of pixels in the bitmap for each "cell"
or Grid Block. Remember that you can scale the pixels using the GridSpacing
parameter in the Maze Simulator config file. For example, if you make the
GridSpacing 0.1 and use 20 pixels per block, then the cells will be 2 meters
square in the simulated world.
</p>
<p>
Wall Thickness is also specified in pixels. It must be less than the Grid Block
size or there will not be any corridors!
</p>
<p>
You can repeatedly generate new mazes until you find one you are happy with by
using File \ Generate New Maze. When you see one you like, use File \ Save As
to save it as a BMP or GIF file.
</p>
<p>
If you wish, you can open the maze in Microsoft Paint and change it or adjust
its size. Note that there are cells marked with green and red which can act
as the start and finish points. However, any clear cell on the left should have
a path to any clear cell on the right of the maze. You can simply recolor the
wall segments as appropriate. Note that colors correspond to textures in the
Maze Simulator.
</p>
<p>
A sample maze is shown below. This was actually edited in Paint to reduce the
padding around the edges. However, remember that the top-left pixel is the
floor color, so do not remove all of the padding. (This is always white in the generated mazes).
</p>
<a href="Images/NewMaze.gif"><img src="Images/NewMaze_small.gif" alt="Sample Maze" border="0" /></a>
<p>
A copy of this image is included with the code. It is called,
not surprisingly, NewMaze.bmp, and should be in store\media\Maze_Textures.
</p>

<h3>Changing the Maze Simulator Config File</h3>
<p>
The Maze Simulator configuration is called MazeSimulator.Config.xml. This
file is located in the ProMRDS\Config folder. Note that you should make a
backup copy of the existing config file first!
</p>
<p>
You can edit this file using Notepad.
The following instructions explain the changes to the file, but you do not have
to make them if you use the supplied file, MazeSimulator.MazeGen.Config.xml.
</p>
<p>
The first thing that needs to be changed is the name of the Maze:<br />
<tt>&lt;Maze&gt;NewMaze.bmp&lt;/Maze&gt;</tt><br />
In this particular example the file must be in store\media\Maze_Textures folder, but you
can move it somewhere else by specifying a path.
</p>
<p>
The ground
color can be changed using the texture. The cellfloor or concrete textures
might be suitable:<br />
<tt>&lt;GroundTexture&gt;concrete.jpg&lt;/GroundTexture&gt;</tt><br />
This texture file should already exist in the store\media folder.
</p>
<p>
The color of the walls can be changed using the corresponding entry
in either the WallTextures or WallColors. You might like to set the
texture for the blue walls to Maze_Textures\bricks.jpg.
The order is Black, Red, Green (Lime), Yellow, Blue, Magenta, Cyan,
White, etc.
<tt>
&lt;WallTextures&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/SolidBlack.bmp&lt;/string&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/SolidRed.bmp&lt;/string&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/SolidLime.bmp&lt;/string&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/SolidYellow.bmp&lt;/string&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/bricks.jpg&lt;/string&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/SolidMagenta.bmp&lt;/string&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/SolidCyan.bmp&lt;/string&gt;<br />
&nbsp;&nbsp;&lt;string&gt;Maze_Textures/SolidBlack.bmp&lt;/string&gt;<br />
...<br />
&lt;/WallTextures&gt;<br />
</tt>
</p>
<p>
You can also change the Height Map so that the start and end points
are a different height from the rest of the walls.
</p>
<p>
Lastly, position the robot so that it starts from the correct location.
This is done as follows:<br />
<tt>
  &lt;RobotStartCellRow&gt;105&lt;/RobotStartCellRow&gt;<br />
  &lt;RobotStartCellCol&gt;-190&lt;/RobotStartCellCol&gt;<br />
</tt>
</p>
<p>
Unfortunately, for historical reasons, the way that you determine this location
is a little complicated. You have to find the pixel location in the bitmap
image where you want to put the robot. For this example it is (25,320) which
is next to the green start point.
The origin in the simulated world is at the center of the map. 
The map is 430x430 pixels, which places the origin at (215,215).
Cell row numbers (vertical coordinates) increase as you move down the image
and cell column numbers (horizontal coordinates) increase from left to right.
So, in this example, the coordinates of the robot are (-190,105), calculated as follows:<br />
Row = 320 - 215 = 105<br />
Col = 25 - 215 = -190
</p>
<p>
NOTE: If you accidentally place the robot inside a wall, then it will
probably be thrown up in the air when the simulation starts and fall
down on its side. Keep adjusting the robot's position and re-running
the Maze Simulator until it starts up OK.
</p>

<h3>Using ExplorerSim</h3>
<p>
If you plan to use the ExplorerSim program with a generated maze, you will have
to modify the config file for ExplorerSim to adjust the size of the map that it
generates. Otherwise you might not see anything on the map! For this example,
a size of 44 meters should be sufficient:<br />
<tt>
  &lt;MapWidth&gt;44&lt;/MapWidth&gt;<br />
  &lt;MapHeight&gt;44&lt;/MapHeight&gt;
</tt>
</p>

<h2>The Challenge</h2>
<p>
Now it is over to you. Write a service that can successfully navigate the maze
using the Webcam or the Laser Range Finder. Processing the images should not
be too hard because walls should be quite different colors from the floor.
You can either handle the images yourself or use a package like RoboRealm.
(Look in the Dashboard code to see how to connect to a webcam and capture images.)
</p>
<p>
If you want to use the Laser Range Finder, look at the code in the ExplorerSim
service.
</p>

<h2>Legal Stuff</h2>
<p>
The original DFS Maze Generator was written by Mike Gold. It was modified
by Trevor Taylor.
</p>
<p>
This program is free for non-commercial use.
</p>

</div>

<hr />
<div class="footer">
Page maintained by:
<a href="m&#97;&#105;&#108;t&#111;:webmaster&#64;promrds&#46;com">webmaster&#64;promrds.com</a><br />
Last Updated: Mar-2008
</div>

</body>
</html>
